//
// Created by zhouyi on 2019/10/24.
//
///////////////////////////////////////////////////////////////////////////
// 设计一个支持 push，pop，top 操作，并能在常数时间内检索到最小元素的栈。
//
// push(x) -- 将元素 x 推入栈中。
// pop() -- 删除栈顶的元素。
// top() -- 获取栈顶元素。
// getMin() -- 检索栈中的最小元素。
// 示例:
//
// MinStack minStack = new MinStack();
// minStack.push(-2);
// minStack.push(0);
// minStack.push(-3);
// minStack.getMin();   --> 返回 -3.
// minStack.pop();
// minStack.top();      --> 返回 0.
// minStack.getMin();   --> 返回 -2.
//
// 来源：力扣（LeetCode）
// 链接：https://leetcode-cn.com/problems/min-stack
// 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
///////////////////////////////////////////////////////////////////////////


//  首先，实现一个栈
// TODO 提取栈里面的最小数据

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

//#define MAX_STACK_SIZE 100
//
//typedef struct {
//    int *data;
//    int topId;
//} MinStack;
//
///** initialize your data structure here. */
//
//MinStack *minStackCreate() {
//    MinStack *stack = malloc(sizeof(MinStack));
//    stack->data = (int *) malloc(MAX_STACK_SIZE * sizeof(int));
//    stack->topId = -1;
//    return stack;
//}
//
//void minStackPush(MinStack *obj, int x) {
//    if (obj->topId == MAX_STACK_SIZE - 1) {
//        // 栈满
//    } else if (obj->topId == -1) {
//        obj->data[0] = x;
//        obj->topId = 0;
//    } else {
//        obj->topId++;
//        obj->data[obj->topId] = x;
//    }
//
//
//}
//
//void minStackPop(MinStack *obj) {
//    if (obj->topId > -1) {
//        obj->topId--;
//    }
//}
//
//int minStackTop(MinStack *obj) {
//    if (obj->topId > -1) {
//        return obj->data[obj->topId];
//
//    }
//}
//
//int minStackGetMin(MinStack *obj) {
//    if (obj->topId > -1) {
//        int minData = INT32_MAX;
//        for (int i = 0; i <= obj->topId; ++i) {
//            if (minData > obj->data[i]) {
//                minData = obj->data[i];
//            }
//        }
//        return minData;
//    }
//}
//
//void minStackFree(MinStack *obj) {
//    free(obj->data);
//    free(obj);
//}

// 范例
typedef struct {
    int *data;
    int *min_data;
    int size;
    int min_size;
    int cur;
    int min_cur;
} MinStack;

/** initialize your data structure here. */

MinStack *minStackCreate() {
    MinStack *minstack = (MinStack *) malloc(sizeof(MinStack));
    minstack->size = 32;
    minstack->cur = 0;
    minstack->data = (int *) malloc(sizeof(int) * (minstack->size));

    minstack->min_size = 32;
    minstack->min_cur = 0;
    minstack->min_data = (int *) malloc(sizeof(int) * minstack->size);

    return minstack;
}

void minStackPush(MinStack *obj, int x) {

    if (obj->cur >= obj->size) {
        obj->size *= 2;
        obj->data = (int *) realloc(obj->data, sizeof(int) * obj->size);
    }

    obj->data[obj->cur] = x;
    obj->cur++;

    if (0 == obj->min_cur) {
        obj->min_data[obj->min_cur] = x;
        obj->min_cur++;
    } else {
        if (x <= obj->min_data[obj->min_cur - 1]) {
            if (obj->min_cur >= obj->min_size) {
                obj->min_size *= 2;
                obj->min_data = (int *) realloc(obj->min_data, sizeof(int) * obj->min_size);
            }

            obj->min_data[obj->min_cur] = x;
            obj->min_cur++;
        }
    }
}

void minStackPop(MinStack *obj) {
    if (0 != obj->cur) {
        obj->cur--;

        if (obj->data[obj->cur] == obj->min_data[obj->min_cur - 1]) {
            obj->min_cur--;
        }
    }

}

int minStackTop(MinStack *obj) {
    if (0 != obj->cur) {
        return obj->data[obj->cur - 1];
    }

    return -1;
}

int minStackGetMin(MinStack *obj) {
    if (0 != obj->min_cur) {
        return obj->min_data[obj->min_cur - 1];
    }

    return -1;
}

void minStackFree(MinStack *obj) {
    free(obj->data);
    free(obj->min_data);
    free(obj);
    obj = NULL;
}


int main(int argc, char *argv[]) {
    MinStack *obj = minStackCreate();

    minStackPush(obj, 15);
    minStackPush(obj, -5);
    minStackPush(obj, 1);
    minStackPush(obj, 6);
    minStackPush(obj, -1);
    minStackPush(obj, 18);
    minStackPush(obj, -9);

//    for (int i = 0; i <= obj->topId; ++i) {
//        printf("Minstack data %d  topId %d \n", obj->data[i], obj->topId);
//    }

    minStackPop(obj);
    minStackPop(obj);
    minStackPop(obj);
    minStackPop(obj);
    printf("====================================\n");
//    for (int i = 0; i <= obj->topId; ++i) {
//        printf("Minstack data %d  topId %d \n", obj->data[i], obj->topId);
//    }
//
    int param_3 = minStackTop(obj);
    printf("minStackTop(obj) %d \n", param_3);

    int param_4 = minStackGetMin(obj);

    printf("minStackGetMin(obj) %d \n", param_4);
//
    minStackFree(obj);

    return 0;
}


